//在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"]
//,["1","0","0","1","0"]]
//输出：4
// 
//
// 示例 2： 
//
// 
//输入：matrix = [["0","1"],["1","0"]]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：matrix = [["0"]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 300 
// matrix[i][j] 为 '0' 或 '1' 
// 
// Related Topics 数组 动态规划 矩阵 
// 👍 797 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Collections;

public class MaximalSquare {
    public static void main(String[] args) {
        Solution solution = new MaximalSquare().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maximalSquare(char[][] matrix) {
            int[][] dp = new int[matrix.length][matrix[0].length];
            int maxSize = 0;
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (i==0 || j==0){
                        if (matrix[i][j]=='1'){
                            dp[i][j]=1;
                        }
                    }
                    else if (matrix[i][j]=='1'){
                        dp[i][j] = 1;
                        dp[i][j] = Collections.min(Arrays.asList(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]))+1;
                    }
                    if(maxSize<dp[i][j]){
                        maxSize = dp[i][j];
                    }

                }
            }
            return maxSize*maxSize;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}